﻿#region COPYRIGHT
//--------------------------------------------------------------------------------
// <copyright file="FastList.cs" company="starLiGHT Entertainment Studios">
//    Copyright (c) 2010 
//       Roland Rosenkranz (Glatzemann@email.de)
// </copyright>
// <license>
//   This file is part of starLiGHT.Core.
//
//   starLiGHT.Core is free software: you can redistribute it and/or modify
//   it under the terms of the GNU Lesser General Public License as published by
//   the Free Software Foundation, either version 3 of the License, or
//   (at your option) any later version.
//
//   starLiGHT.Core is distributed in the hope that it will be useful,
//   but WITHOUT ANY WARRANTY; without even the implied warranty of
//   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
//   GNU Lesser General Public License for more details.
//
//   You should have received a copy of the GNU Lesser General Public License
//   along with starLiGHT.Core. If not, see http://www.gnu.org/licenses/.
//    
//   ADDITIONAL (commercial) LICENSES for starLiGHT.Core are available on request.
// </license>
// <version>
// **************[ starLiGHT.Engine SVN ]**********************
// * $Rev:: 620                   $:  Revision of last commit *
// * $Author:: unknown            $:  Author of last commit   *
// * $Date:: 2010-12-07 15:23:58 #$:  Date of last commit     *
// ************************************************************
// </version>
//--------------------------------------------------------------------------------
#endregion

namespace starLiGHT.Collections
{
    #pragma warning disable 0420 // a reference to a volatile field will not be treated as volatile

    #region Using Statements
    using System;
    using System.Collections;
    using System.Collections.Generic;
    using System.Linq;
    using System.Text;
    using System.Threading;

    #endregion

    /// <summary>
    /// The FastList is very similar to the standard generic List of .NET because both are working
    /// in a similar way. Both of them are using growing arrays for storing data. The advantage of the
    /// FastList over the .NET-List are: <br/><br/>
    /// - Clearing the list: The FastList is approx. 10 times faster<br/>
    /// - Removing elements from the beginning: The FastList is approx. 10 times faster<br/>
    /// - Enumerating the list: The FastList is approx. 3 times faster<br/>
    /// <br/>
    /// The FastList is faster at clearing, because it doesn't really clears the list and doesn't free
    /// any memory. It resets the element counter only to zero. When you add new elements they will overwrite 
    /// the old unused elements. Removing single elements from the list is working in a similar way. No memory 
    /// is freed in this case.
    /// </summary>
    /// <typeparam name="T">
    /// The object type that should be stored in the FastList.
    /// </typeparam>
    public class FastList<T> : IEnumerable<T>, IList<T>
    {
        public const int DefaultSize = 512;

        private T[] itemArray;
        private int elementCount;
        private int actualCapacity;

        public FastList()
        {
            this.itemArray = new T[DefaultSize];
            this.elementCount = 0;
            this.actualCapacity = DefaultSize;
        }

        public FastList(int size)
        {
            this.itemArray = new T[size];
            this.elementCount = 0;
            this.actualCapacity = size;
        }

        public FastList(T[] values)
        {
            this.itemArray = new T[Math.Max(DefaultSize, values.Length)];
            this.elementCount = values.Length;
            this.actualCapacity = this.itemArray.Length;
            Array.Copy(values, this.itemArray, this.elementCount);
        }

        public int Count
        {
            get { return this.elementCount; }
        }

        public bool IsReadOnly
        {
            get
            {
                return false;
            }
        }

        public T this[int index]
        {
            get
            {
                if (index >= this.elementCount || this.elementCount == 0 || index < 0)
                {
                    throw new IndexOutOfRangeException("index have to be between 0 and " + this.elementCount);
                }

                return this.itemArray[index];
            }

            set
            {
                if (index >= this.elementCount || this.elementCount == 0 || index < 0)
                {
                    throw new IndexOutOfRangeException("index have to be between 0 and " + this.elementCount);
                }

                this.itemArray[index] = value;
            }
        }

        public Enumerator GetEnumerator()
        {
            return new Enumerator(this);
        }

        IEnumerator<T> IEnumerable<T>.GetEnumerator()
        {
            return new Enumerator(this);
        }

        IEnumerator IEnumerable.GetEnumerator()
        {
            return new Enumerator(this);
        }

        public void Add(T item)
        {
            if (this.elementCount + 1 > this.actualCapacity)
            {
                this.GrowBuffer();
            }

            this.itemArray[this.elementCount] = item;
            this.elementCount++;
        }

        public void Add(ref T item)
        {
            if (this.elementCount + 1 > this.actualCapacity)
            {
                this.GrowBuffer();
            }

            this.itemArray[this.elementCount] = item;
            this.elementCount++;
        }

        public void AddRange(IList<T> items)
        {
            int count = items.Count<T>();

            if (this.elementCount + count > this.actualCapacity)
            {
                this.GrowBuffer();
            }

            for (int i = 0; i < count; i++)
            {
                this.itemArray[this.elementCount] = items[i];
                this.elementCount++;
            }
        }

        public void AddRange(ref IList<T> items)
        {
            int count = items.Count<T>();

            if (this.elementCount + count > this.actualCapacity)
            {
                this.GrowBuffer();
            }

            for (int i = 0; i < count; i++)
            {
                this.itemArray[this.elementCount] = items[i];
                this.elementCount++;
            }
        }

        public int IndexOf(T element)
        {
            for (int i = 0; i < this.elementCount; i++)
            {
                if (this.itemArray[i].Equals(element))
                {
                    return i;
                }
            }

            return -1;
        }

        public void Insert(int index, T element)
        {
            if (this.elementCount + 1 > this.actualCapacity)
            {
                this.GrowBuffer();
            }

            Array.Copy(this.itemArray, index, this.itemArray, index + 1, this.elementCount - index);
            this.itemArray[index] = element;
            this.elementCount++;
        }

        /// <summary>
        /// Copies the entire FastList&lt;T&gt; to a compatible one-dimensional array,
        /// starting at the specified index of the target array.
        /// </summary>
        /// <param name="target">
        /// The one-dimensional Array that is the destination of the elements copied from FastList. The Array must have zero-based indexing.
        /// </param>
        /// <param name="arrayIndex">
        /// The zero-based index in array at which copying begins.
        /// </param>
        public void CopyTo(T[] target, int arrayIndex)
        {
            if (target.Length < arrayIndex + this.elementCount)
            {
                throw new IndexOutOfRangeException("The target array is not big enough to copy all elements.");
            }

            for (int i = 0; i < this.elementCount; i++)
            {
                target[arrayIndex++] = this.itemArray[i];
            }
        }

        public bool Remove(T element)
        {
            for (int i = 0; i < this.elementCount; i++)
            {
                if (this.itemArray[i].Equals(element))
                {
                    this.RemoveAt(i);
                    return true;
                }
            }

            return false;
        }

        public void RemoveAt(int index)
        {
            if ((index < 0) || (index >= this.elementCount))
            {
                throw new IndexOutOfRangeException();
            }

            int newCount = this.elementCount - 1;

            if (index < newCount)
            {
                this.itemArray[index] = this.itemArray[newCount];
            }

            this.elementCount = newCount;
        }

        public bool TryPopFront(out T result)
        {
            if (this.elementCount == 0)
            {
                result = default(T);
                return false;
            }

            result = this.itemArray[0];
            this.RemoveAt(0);

            return true;
        }

        public void Clear()
        {
            this.elementCount = 0;
        }

        public T[] GetBuffer()
        {
            return this.itemArray;
        }

        public T[] ToArray()
        {
            T[] result = new T[this.elementCount];
            Array.Copy(this.itemArray, result, this.elementCount);
            return result;
        }

        public void Sort(IComparer<T> comparer)
        {
            Array.Sort(this.itemArray, 0, this.elementCount, comparer);
        }

        public bool Contains(T item)
        {
            if (item == null)
            {
                for (int j = 0; j < this.elementCount; j++)
                {
                    if (this.itemArray[j] == null)
                    {
                        return true;
                    }
                }

                return false;
            }

            EqualityComparer<T> comparer = EqualityComparer<T>.Default;
            for (int i = 0; i < this.elementCount; i++)
            {
                if (comparer.Equals(this.itemArray[i], item))
                {
                    return true;
                }
            }

            return false;
        }

        private void GrowBuffer()
        {
            T[] oldItems = this.itemArray;
            this.actualCapacity += this.actualCapacity;
            this.itemArray = new T[this.actualCapacity];
            Array.Copy(oldItems, this.itemArray, this.elementCount);
        }

        public struct Enumerator : IEnumerator<T>
        {
            private FastList<T> list;
            private int index;

            public Enumerator(FastList<T> list)
            {
                this.list = list;
                this.index = -1;
            }

            public T Current
            {
                get { return this.list.itemArray[this.index]; }
            }

            object System.Collections.IEnumerator.Current
            {
                get { return this.list.itemArray[this.index]; }
            }

            public void Dispose()
            {
            }

            public void SetCurrent(ref T newValue)
            {
                this.list.itemArray[this.index] = newValue;
            }

            public bool GetNext(out T nextItem)
            {
                this.index += 1;

                if (this.index < this.list.elementCount)
                {
                    nextItem = this.list.itemArray[this.index];

                    return true;
                }
                else
                {
                    nextItem = default(T);

                    return false;
                }
            }

            public bool MoveNext()
            {
                this.index += 1;

                return this.index < this.list.elementCount;
            }

            public void Reset()
            {
                this.index = -1;
            }

            public void RemoveCurrent()
            {
                this.list.RemoveAt(this.index);
                this.index -= 1;
            }
        }
    }
}
